#include <stdio.h>
#include <stdlib.h>

// 用双向循环链表保存数据实体，用哈希保存链表节点映射，便于查询中
struct node {
    int key;
    int val;
    struct node *prev;
    struct node *next;
};


typedef struct hash_node{
    int key;
    struct node *map;
    struct hash_node *next;
} hash_node_t;

typedef struct {
    int uid;
    hash_node_t *head;
    hash_node_t *tail;
} hash_unit_t;

typedef struct {
    int tsize;
    int count;
    hash_unit_t **units;
} hash_table_t;


typedef struct {
    int capacity;
    int count;
    struct node *cdll;    // cdll->next指向数据头，cdll->prev指向数据尾
    hash_table_t *tbl;  // 哈希表保存链表节点映射，便于快速查询
} lru_t;



/************************ 链表操作 *****************************/
void cdll_add_head(struct node *cdll, struct node *node) {
    node->next = cdll->next; node->prev = cdll;
    cdll->next->prev = node; cdll->next = node;
}

// 将node从链表中取出
void cdll_drop(struct node *cdll, struct node *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}
/**************************************************************/



/************************ 哈希表操作 ****************************/
static hash_unit_t *create_hash_unit(int uid) {
    hash_unit_t *unit = malloc(sizeof(*unit));
    unit->uid = uid;
    unit->head = NULL;
    unit->tail = NULL;
    return unit;
}
hash_table_t *create_hash_table(int tsize) {
    hash_table_t *tbl = malloc(sizeof(*tbl));
    tbl->tsize = tsize;
    tbl->count = 0;
    tbl->units = malloc(sizeof(hash_unit_t *) * tsize);
    for (int i = 0; i < tsize; i++) {
        tbl->units[i] = create_hash_unit(i);
    }
    return tbl;
}
int myhash(hash_table_t *tbl, int key) {
    return (key % tbl->tsize);
}

void hash_add(hash_table_t *tbl, struct node *node) {
    hash_unit_t *unit = tbl->units[myhash(tbl, node->key)];
    
    hash_node_t *hashnode = malloc(sizeof(*hashnode));
    hashnode->key = node->key;
    hashnode->map = node;
    hashnode->next = NULL;
    
    if (unit->head == NULL) {
        unit->head = unit->tail = hashnode;
    } else {
        unit->tail->next = hashnode;
        unit->tail = hashnode;
    }
    tbl->count++;
}

void hash_find(hash_table_t *tbl, int key, hash_node_t **res) {
    hash_unit_t *unit = tbl->units[myhash(tbl,key)];
    if (unit->head == NULL) {
        *res = NULL;
    } else {
        hash_node_t *prev, *cur;
        prev = cur = unit->head;
        while (cur && cur->key != key) {
            prev = cur; cur = cur->next;
        }
        if (cur != NULL) *res = cur;
        else *res = NULL;
    }
}

void hash_del(hash_table_t *tbl, int key) {
    hash_unit_t *unit = tbl->units[myhash(tbl,key)];
    if (unit->head == NULL) {
        // unit is empty
    } else {
        hash_node_t *prev, *cur;
        prev = cur = unit->head;
        while (cur && cur->key != key) {
            prev = cur; cur = cur->next;
        }
        hash_node_t *del;
        if (cur != NULL) {
            if (prev == cur) {
                unit->head = cur->next;
            } else {
                prev->next = cur->next;
            }
            cur->map = NULL;
            free(cur);
            tbl->count--;
        } else {
            // not found
        }
    }
}
/****************************************************************/


/************************ LRU操作 *****************************/
// 传入要管理的数据量
lru_t *LRU_create(int datasize) {
    lru_t *lru = malloc(sizeof(*lru));
    lru->capacity = datasize;
    lru->count = 0;
        
    lru->cdll = malloc(sizeof(struct node));
    lru->cdll->prev = lru->cdll->next = lru->cdll;
    
    lru->tbl = create_hash_table(datasize/8 + 1);
    return lru;
}

// 查看key对应的val
int LRU_get(lru_t *lru, int key) {
    hash_node_t *ret;
    hash_find(lru->tbl, key, &ret);
    if (ret == NULL) return -1;
    else {
        cdll_drop(lru->cdll, ret->map);    //取出节点
        cdll_add_head(lru->cdll, ret->map);    //放回到表头
        return ret->map->val;
    }
}

// 添加或更新key-val
void LRU_set(lru_t *lru, int key, int val) {
    hash_node_t *ret;
    hash_find(lru->tbl, key, &ret);
    if (ret == NULL) {    // 不存在
        struct node *node = malloc(sizeof(*node));
        node->key = key;
        node->val = val;
        // lru缓存已满，丢弃尾节点
        if (lru->count == lru->capacity) {
            struct node *temp = lru->cdll->prev;    
            cdll_drop(lru->cdll, temp);
            hash_del(lru->tbl, temp->key);
            free(temp); lru->count--;
        } 
        
        cdll_add_head(lru->cdll, node);
        hash_add(lru->tbl, node);
        lru->count++;
    }
    else {    // 节点已存在，更新节点值
        ret->map->val = val;
        if (ret->map == lru->cdll->next)    //头节点 
            ;
        else {
            cdll_drop(lru->cdll, ret->map);
            cdll_add_head(lru->cdll, ret->map);
        }
    }
}
/****************************************************************/



/******************** 销毁操作 ********************************/
void cdll_distroy(struct node *cdll) {
    struct node *p = cdll->next, *del;
    while (p != cdll) {
        del = p;
        p = p->next;
        free(del); 
    }
    free(cdll);
}

static void hash_unit_distroy(hash_unit_t *unit) {
    hash_node_t *head = unit->head;
    while (head != NULL) {
        hash_node_t *del = head;
        head = head->next;
        free(del); 
    }
    free(unit);
}
void hash_table_distroy(hash_table_t *tbl) {
    for (int i = 0; i < tbl->tsize; i++) {
        hash_unit_distroy(tbl->units[i]);
    }
    free(tbl);
}

void LRU_distroy(lru_t *lru) {
    cdll_distroy(lru->cdll);
    hash_table_distroy(lru->tbl);
    free(lru);
}
/****************************************************************/


/******************* 显示操作 ************************************/

void display_cdll(struct node *cdll)
{
	struct node *p = cdll->next;
    printf("cdll: ");
	while (p != cdll) {
		printf("%d-%d ",p->key,p->val);
		p = p->next;
	}
    printf("\n");
}

void display_hash_unit(hash_unit_t *unit) {
    printf("uid %d: ", unit->uid);
    hash_node_t *p = unit->head;
    while (p != NULL) {
        printf("%d-%d ", p->map->key, p->map->val);
        p = p->next;
    }
    printf("\n");
}
void display_hash_table(hash_table_t *tbl) {
    printf("tbl {tsize:%d count:%d}\n", tbl->tsize, tbl->count);
    for (int i = 0; i < tbl->tsize; i++)
        display_hash_unit(tbl->units[i]);
}

void display_lru(lru_t *lru) {
    printf("lru { capacity:%d count:%d}\n", lru->capacity, lru->count);
    display_cdll(lru->cdll);
    display_hash_table(lru->tbl);
}
void main()
{

	lru_t* lru = LRU_create(3);

	//未溢出时插入没有问题
	LRU_set(lru, 233, 1);
	LRU_set(lru, 111, 2);
	LRU_set(lru, 6, 100);
    // LRU_set(lru, 12, 80);
    display_lru(lru);
    printf("\n");

	// 取缓存没有问题
	LRU_get(lru, 111);
    display_cdll(lru->cdll);

    // 将已存在结节调整位置没有问题
    LRU_set(lru, 6, 132);
    display_cdll(lru->cdll);

	// lru满时没问题
    LRU_set(lru, 9, 132);
    display_cdll(lru->cdll);
}
